# ifndef __HuffmanCode_H_
# define __HuffmanCode_H_

	//
	// Huffman code table builder utility.
	//
	// NOTE: resulting codes lengths are assumed to be no longer then 32 bit.
	//

class CHuffmanCodeTable {
  public:
	CHuffmanCodeTable () :
		m_cN (0),
		m_pcP     (NULL),
		m_pcLen   (NULL),
		m_pdwCode (NULL),
		m_cNonEmptyCodes (0),
		m_bFlat (false),
		m_bCanBeFlat (false)
	{}
	CHuffmanCodeTable (size_t _cN, bool _bCanBeFlat = false) {Init (_cN, _bCanBeFlat);}
	~CHuffmanCodeTable () {
		delete [] m_pcP;
		delete [] m_pcLen;
		delete [] m_pdwCode;
	}

	void Init (size_t _cN, bool _bCanBeFlat) {
		m_cN = _cN;
		m_cNonEmptyCodes = 0;

		m_pcP     = new size_t [_cN*2];
		m_pcLen   = new size_t [_cN];
		m_pdwCode = new DWORD  [_cN];
		::memset (m_pcP,     0, sizeof (* m_pcP)*_cN*2);
		::memset (m_pcLen,   0, sizeof (* m_pcLen)*_cN);
		::memset (m_pdwCode, 0, sizeof (* m_pdwCode)*_cN);
		m_bCanBeFlat = _bCanBeFlat;
	}

	void AddValue (size_t _cValue) {
		assert (_cValue < m_cN);
		if (m_pcP [_cValue] == 0) {
			++ m_cNonEmptyCodes;
			assert (m_cNonEmptyCodes <= m_cN);
		}
		++ m_pcP [_cValue];
	}

	void Build ();

	size_t GetCodes () const {return m_cN;}
	size_t GetNonEmptyCodes () const {return m_cNonEmptyCodes;}

	bool IsCodePresent (size_t _cValue) const {
		assert (_cValue < m_cN);
		// NOTE: it is possible to have just one value in the table => with code len=0.
		return GetCodeLen (_cValue) > 0 || m_pcP [_cValue] != 0;
	}
	size_t GetCodeLen (size_t _cValue) const {
		assert (_cValue < m_cN);
		return m_pcLen [_cValue];
	}
	const BYTE * GetCode (size_t _cValue) const {
		assert (_cValue < m_cN);
		return reinterpret_cast<const BYTE *> (& m_pdwCode [_cValue]);
	}
	const DWORD GetCodeValue (size_t _cValue) const {
		assert (_cValue < m_cN);
		return m_pdwCode [_cValue];
	}

	void BuildFlat ();
	bool IsFlat () const {return m_bFlat;}
  private:
	bool _BuildTree ();
	bool _VisitNode (size_t * _pTreeLeft, size_t * _pTreeRight, size_t _cNode, DWORD _dwCode, size_t _cLen);

	size_t m_cN;
	size_t * m_pcP;

	size_t * m_pcLen;
	DWORD  * m_pdwCode;

	size_t m_cNonEmptyCodes;
	size_t m_c17BitCodes;
	bool m_bFlat;
	bool m_bCanBeFlat;
};

# endif // __HuffmanCode_H_